智能优化算法应用：基于麻雀搜索优化K

K-Means算法是一种无监督分类算法，假设有无标签数据集： X = [ x 1 , x 2 , . . . , x n ] (1) X = [x_1,x_2,...,x_n] \tag{1} X=[x1​,x2​,...,xn​](1) 该算法的任务是将数据集聚类成 k k k簇 C = C 1 , C 2 , . . . , C k C = C_1,C2,...,C_k C=C1​,C2,...,Ck​，最小化损失函数为: E = ∑ i = 1 k ∑ x ∈ C i ∣ ∣ x − u i ∣ ∣ 2 (2) E = \sum_{i=1}^k\sum_{x\in C_i}||x-u_i||^2 \tag{2} E=i=1∑k​x∈Ci​∑​∣∣x−ui​∣∣2(2) 其中 u i u_i ui​为簇的中心点： u i = 1 ∣ C i ∣ ∑ x ∈ C i x (3) u_i = \frac{1}{|C_i|}\sum_{x\in C_i}x \tag{3} ui​=∣Ci​∣1​x∈Ci​∑​x(3) 要找到以上问题的最优解需要遍历所有可能的簇划分，K-Mmeans算法使用贪心策略求得一个近似解，具体步骤如下：

1.在样本中随机选取 k k k个样本点充当各个簇的中心点 { u 1 , u 2 , . . . , u k } \{u_1,u_2,...,u_k\} {u1​,u2​,...,uk​}

2.计算所有样本点与各个簇中心之间的距离 d i s t ( x i , u j ) dist(x_i,u_j) dist(xi​,uj​)，然后把样本点划入最近的簇中 x i ∈ u n e a r e s t x_i \in u_{nearest} xi​∈unearest​

3.根据簇中已有的样本点，重新计算簇中心 u i = 1 ∣ C i ∣ ∑ x ∈ C i x u_i = \frac{1}{|C_i|}\sum_{x\in C_i}x ui​=∣Ci​∣1​x∈Ci​∑​x

4.重复2、3

K-means算法得到的聚类结果严重依赖与初始簇中心的选择，如果初始簇中心选择不好，就会陷入局部最优解.因此初始簇中心的选择非常重要。本文利用麻雀优化算法对初始簇中心进行优化，改进其容易陷入局部最优的特点。

麻雀搜索算法的具体原理参考博客：https://blog.csdn.net/u011835903/article/details/108830958

适应度函数：利用麻雀搜索算法改进kmeans时，以聚类中心作为麻雀算法的优化变量，适应度函数设计如下： f i t n e s s = ∑ i = 1 k ∑ x ∈ C i ∣ ∣ x − u i ∣ ∣ 2 fitness = \sum_{i=1}^k\sum_{x\in C_i}||x-u_i||^2 fitness=i=1∑k​x∈Ci​∑​∣∣x−ui​∣∣2 该适应度函数与kmeans的最小损失函数一致。

算法的具体流程如下：

1.随机抽样待分类数据点，作为麻雀搜索聚类候选点。

2.利用麻雀搜索算法搜索最小损失的的聚类点。

3.将这些聚类点作为kmeans算法的初始聚类点。

4.利用kmeans获得最终的聚类点。

将基于麻雀搜索优化的Kmeans算法用于图像的分割实验。对于图像，选取10%的像素点作为聚类候选点。

对于灰度图像聚类个数2，3，4的结果如下图所示：

对于彩色图像的聚类效果如下图所示：

收敛曲线：

个人资料介绍